package com.dycong.common.leetcode.yi;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-08-08
 * Time: 16:44
 */
public class LRUCacheV {

    private int capacity;
    private LinkNode first = null;
    private LinkNode last = null;
    private Map<Integer, LinkNode> cacheMap = null;


    public LRUCacheV(int capacity) {
        this.capacity = capacity;
        cacheMap = new HashMap<>(capacity);
    }

    public int get(int key) {
        LinkNode res = cacheMap.get(key);
        if (res == null) {
            return -1;
        }
        moveNodeToFirst(res);
        return res.val;

    }

    public void put(int key, int value) {
        LinkNode temp = cacheMap.get(key);
        if (temp == null) {
            int size = cacheMap.size();
            if (size >= capacity) {
                removeLastNode();
            }
            temp = new LinkNode();
            temp.key = key;
        }
        temp.val = value;
        moveNodeToFirst(temp);
        cacheMap.put(key, temp);
    }

    private void removeLastNode() {
        LinkNode tmp = last;
        last = last.pre;
        if (last == null) {
            first = last = null;
        } else {
            last.next = null;
        }
        cacheMap.remove(tmp.key);
    }

    private void moveNodeToFirst(LinkNode node) {

        if (first == node) {
            return;
        }
        if (last == null) {
            last = first = node;
            return;
        }
        if (last == node) {
            last = last.pre;
        }
        if (node.next != null) {
            node.pre.next = node.next;
        }

        //把节点迁移到最前
        first.pre = node;
        node.next = first;
        node.pre = null;

    }

    // 双向链表的原因，是在把某个节点移动到头节点时，需要把这个节点的上一个节点，指向这个节点的下一个节点
    class LinkNode {

        LinkNode pre;
        LinkNode next;
        int key;
        int val;
    }
}




